package class8;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 求线段重合数量
 * [1,7]
 * [2,6]
 * [3,9]
 * + 1 2 3 4 5 6 7 8 9
 * + |-----------|
 * +   |-------|
 * +     |-----------|
 * 求重合数
 */
public class Code10_maxCoverCount {
    public static void main(String[] args) {
        int[][] matrix = new int[][]{
                {1, 7},
                {4, 9},
                {2, 5},
                {6, 10}
        };
        int max = maxCover(matrix);
        System.out.println("max = " + max);
    }

    public static int maxCover(int[][] m) {
        Line[] lines = new Line[m.length];
        for (int i = 0; i < lines.length; i++) {
            lines[i] = new Line(m[i][0], m[i][1]);
        }
        // 将线段数组排好序
        Arrays.sort(lines, new StartComparator());
        // 小根堆，存放每一条线段的结尾数值
        PriorityQueue<Integer> heap = new PriorityQueue();
        int max = 0;
        for (int i = 0; i < lines.length; i++) {
            while (!heap.isEmpty() && heap.peek() <= lines[i].start) {
                heap.poll();
            }
            heap.add(lines[i].end);
            max = Math.max(max, heap.size());
        }
        return max;
    }

    public static class Line {
        public int start;
        public int end;

        public Line(int s, int e) {
            start = s;
            end = e;
        }
    }

    // 对线段进行排序
    public static class StartComparator implements Comparator<Line> {
        @Override
        public int compare(Line o1, Line o2) {
            return o1.start - o2.start;
        }
    }
}
